//
//  main.c
//  BothwayChain
//
//  Created by Shawn Li on 2020/4/15.
//  Copyright © 2020 Shawn. All rights reserved.
//

//此工程主要演示双向链表的实现
#include <stdio.h>
#include "stdlib.h"
//#include "math.h"
//#include "time.h"

#define MAXSIZE 20

#define SUCCESS 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

typedef int ElementType;

typedef int Status;

typedef struct ChainNode{
    //    数据域
    ElementType data;
    //    前驱指针域
    struct ChainNode *front;
    //    后继指针域
    struct ChainNode *next;
}ChainNode, *ChainNodePtr;

//定义双向链表
typedef struct BothwayChain{
//    链表的头结点，当然你也可以不使用头结点，那样你需要最首元结点进行额外操作
    ChainNodePtr chain;
//    链表的长度
    int count;
}BothwayChain;


/// 链表的初始化
/// @param c 链表
Status chainInit(BothwayChain *c){
//    为了首元结点的操作一致性我们引出头结点。
    c->chain = (ChainNodePtr)malloc(sizeof(ChainNode));
    c->chain->front = c->chain->next = NULL;
    c->count = 0;
    printf("链表初始化完毕！------------------------------------\n\n");
    return SUCCESS;
}

/// 使用一个数组来初始化一个链表
/// @param c 链表
/// @param a 数组
/// @param n 数组的长度
Status chainInitWithArr(BothwayChain *c, int a[], int n){

    chainInit(c);
    //    记录链表的尾
    ChainNodePtr tail;
    
    tail = c->chain;
    
    for (int i = 0; i < n; i++) {
        ChainNodePtr k = (ChainNodePtr)malloc(sizeof(ChainNode));
        k->data = a[i];
        k->next = NULL;
//        尾插法插入数据，注意对于操作处俩端的指针丢需要进行处理。
        k->front = tail;
        tail->next = k;
//        记录新的尾
        tail = k;
//        长度增加
        c->count++;
    }
    
    return SUCCESS;
}

/// 链表清空
/// @param c 链表
Status chainClear(BothwayChain *c){
    ChainNodePtr p, temp;
//    清空链表的时候保留头结点
    p = c->chain->next;
    
    while (p) {
        temp = p;
        p = p->next;
        
//        这里的逻辑类似于删除
        temp->front->next = temp->next;
        if (temp->next) {
            temp->next->front = temp->front;
        }
        
//        这一步省略，temp已经被释放了
        temp->front = temp->next = NULL;
        free(temp);
    }
    return SUCCESS;
}

/// 判断链表是否为空
/// @param c 链表
Status chainIsEmpty(BothwayChain c){
//    此处你也可以使用count来进行判断
    return NULL == c.chain->next;
}

/// 遍历并输出链表
/// @param c 链表
Status chainPrint(BothwayChain c){
    
    if (chainIsEmpty(c)) {
        printf("链表为空，无需输出！\n");
        return ERROR;
    }
    ChainNodePtr p;
    p = c.chain->next;
    
    printf("输出链表：\n");
    while (p) {
        printf("%d, ", p->data);
        p = p->next;
    }
    printf("\n\n");
    
    return SUCCESS;
}

/// 获取链表的长度
/// @param c 链表
int chainGetCount(BothwayChain c){
    return c.count;
}

/// 在特定位置插入新的元素
/// @param c 链表
/// @param index 待插入位置
/// @param e 待插入元素
Status chainInsert(BothwayChain *c, int index, ElementType e){
    if (NULL == c) {
        printf("链表不存在，无法插入元素！\n");
        return ERROR;
    }
    
    ChainNodePtr p = c->chain;
    
//    寻找插入位置的前驱结点
    for (int i = 1; i < index && NULL != p; i++, p = p->next) ;
    
    if (NULL == p) {
        printf("没有找到正确的位置，无法插入元素！\n");
        return ERROR;
    }
    
    ChainNodePtr k = (ChainNodePtr)malloc(sizeof(ChainNode));
    k->data = e;
    
    k->next = p->next;
    
//    注意此处可能插在最后一位，此时 k->next = NULL 所以不能处理它的前驱指针域。
    if (NULL != k->next) {
        k->next->front = k;
    }
    
    k->front = p;
    p->next = k;
    c->count++;
    
    return SUCCESS;
}


/// 删除特定位置的结点
/// @param c 链表
/// @param index 待删除位置
/// @param e 删除结点值带回
Status chainDelete(BothwayChain *c, int index, ElementType *e){
    if (NULL == c->chain) {
        printf("链表不存在，无法操作！");
        return ERROR;
    }
    ChainNodePtr p = c->chain;
    
    for (int i = 1; i < index && NULL != p; i++, p = p->next) ;
    
    if (NULL == p) {
        printf("没有找到正确的位置，无法操作！");
        return ERROR;
    }
    
    ChainNodePtr temp = p->next;
    p->next = p->next->next;
    
//    注意此处可能删除在最后一位，此时 p->next = NULL 所以不能处理它的前驱指针域。
    if (p->next) {
        p->next->front = p;
    }
   
//    带回值
    *e = temp->data;
    
//    这一步可以省略，因为temp反正是要释放的。
//    temp->front = temp->next == NULL;
    free(temp);
    
    return SUCCESS;
}

int main(int argc, const char * argv[]) {
    
    printf("Hello, World!\n");
    
    BothwayChain c;
    ElementType e;
    
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    chainInitWithArr(&c, a, 16);
    chainPrint(c);
    
    chainInit(&c);
    
    if (chainInsert(&c, 2, 99999)) {
        chainPrint(c);
    }
    
    for (int i = 0; i < 10; i++) {
        if (chainInsert(&c, 1, 111 * i)) {
            chainPrint(c);
        }
    }
    
    for (int i = 0; i < 10; i++) {
        if (chainDelete(&c, 1, &e)) {
            printf("删除元素为：%d", e);
            chainPrint(c);
        }
    }
    
    
    return 0;
}
